﻿#define _CRT_SECURE_NO_WARNINGS 1
//给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
//
//插入排序 算法的步骤 :
//
//插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
//每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
//重复直到所有输入数据插入完为止。
//下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
//
//对链表进行插入排序。
//
//
//
//
//
//示例 1：
//
//
//
//输入: head = [4, 2, 1, 3]
//输出 : [1, 2, 3, 4]
//示例 2：
//
//
//
//输入: head = [-1, 5, 3, 4, 0]
//输出 : [-1, 0, 3, 4, 5]
//
//
//提示：
//
//列表中的节点数在 [1, 5000]范围内
//- 5000 <= Node.val <= 5000
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/insertion-sort-list
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

 //选择排序:
struct ListNode* insertionSortList(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    struct ListNode* cur = head;
    while (cur)
    {
        struct ListNode* cmp = cur;
        struct ListNode* copy = cur->next;
        while (copy)
        {
            if (cmp->val > copy->val)
            {
                cmp = copy;
            }
            copy = copy->next;
        }
        if (cmp != cur)
        {
            int tmp = cur->val;
            cur->val = cmp->val;
            cmp->val = tmp;
        }
        cur = cur->next;
    }
    return head;

}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

 //插入排序：
struct ListNode* insertionSortList(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;

    //1、初始条件
    struct ListNode* sortHead = head;
    struct ListNode* cur = head->next;
    sortHead->next = NULL;//将第一个头拿出来，后面的元素在此基础之上插入

    while (cur)//2、终止条件
    {
        // 3、迭代条件
        struct ListNode* next = cur->next;

        //将cur结点插入前面有序区间
        struct ListNode* p = NULL, * c = sortHead;
        while (c)
        {
            if (cur->val < c->val)
            {
                if (p == NULL)
                {
                    cur->next = c;
                    sortHead = cur;
                }
                else
                {
                    p->next = cur;
                    cur->next = c;
                }
                break;
            }
            else
            {
                p = c;
                c = c->next;
            }
        }
        if (c == NULL)
        {
            p->next = cur;

            cur->next = c;
        }
        cur = next;
    }

    return sortHead;
}

//将上面内部break的拿出来合并比较简洁，如下：

//插入排序：
struct ListNode* insertionSortList(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;

    //1、初始条件
    struct ListNode* sortHead = head;
    struct ListNode* cur = head->next;
    sortHead->next = NULL;//将第一个头拿出来，后面的元素在此基础之上插入

    while (cur)//2、终止条件
    {
        // 3、迭代条件
        struct ListNode* next = cur->next;

        //将cur结点插入前面有序区间
        struct ListNode* p = NULL, * c = sortHead;
        while (c)
        {
            if (cur->val < c->val)
            {
                break;
            }
            else
            {
                p = c;
                c = c->next;
            }
        }
        if (p == NULL)
        {
            cur->next = c;
            sortHead = cur;
        }
        else
        {
            p->next = cur;
            cur->next = c;
        }

        cur = next;

    }

    return sortHead;
}